#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int comp(const void* s1, const void* s2)
{
    return *(int*)s1 - *(int*)s2;
}
int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes)
{
    int** ans = malloc(sizeof(int*) * 10000);
    *returnColumnSizes = malloc(sizeof(int) * 1001);
    int count = 0;
    qsort(nums, numsSize, sizeof(int), comp);
    if (numsSize < 4)
    {
        *returnSize = 0;
        return NULL;
    }
    int i = 0;
    for (i = 0; i < numsSize - 3; i++)
    {
        if (i > 0 && nums[i] == nums[i - 1])
            continue;
        if ((long)nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target)
            break;
        if ((long)nums[i] + nums[numsSize - 3] + nums[numsSize - 2] + nums[numsSize - 1] < target) {
            continue;
        }
        for (int j = i + 1; j < numsSize - 2; j++)
        {
            if (j > i + 1 && nums[j] == nums[j - 1]) {
                continue;
            }
            if ((long)nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                break;
            }
            int right = numsSize - 1;
            int left = j + 1;
            if (j > i + 1 && nums[j] == nums[j - 1])
                continue;
            while (left < right)
            {
                long sum = (long)nums[i] + nums[j] + nums[left] + nums[right];
                if (sum == target)
                {
                    (*returnColumnSizes)[count] = 4;
                    int* tmp = malloc(sizeof(int) * 4);
                    tmp[0] = nums[i];
                    tmp[1] = nums[j];
                    tmp[2] = nums[left];
                    tmp[3] = nums[right];
                    ans[count++] = tmp;
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    left++;
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    right--;
                }
                else if (sum > target)
                    right--;
                else if (sum < target)
                    left++;
            }
        }
    }
    *returnSize = count;
    return ans;
}




//char phoneMap[8][5] = { "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
//
//char* digits_tmp;
//int digits_size;
//
//char** combinations;
//int combinations_size;
//
//char* combination;
//int combination_size;
//
//void backtrack(int index) {
//    if (index == digits_size) {
//        char* tmp = malloc(sizeof(char) * (combination_size + 1));
//        memcpy(tmp, combination, sizeof(char) * (combination_size + 1));
//        combinations[combinations_size++] = tmp;
//    }
//    else {
//        char digit = digits_tmp[index];
//        char* letters = phoneMap[digit - '2'];
//        int len = strlen(letters);
//        for (int i = 0; i < len; i++) {
//            combination[combination_size++] = letters[i];
//            combination[combination_size] = 0;
//            backtrack(index + 1);
//            combination[--combination_size] = 0;
//        }
//    }
//}
//
//char** letterCombinations(char* digits, int* returnSize) {
//    combinations_size = combination_size = 0;
//    digits_tmp = digits;
//    digits_size = strlen(digits);
//    if (digits_size == 0) {
//        *returnSize = 0;
//        return combinations;
//    }
//    int num = 1;
//    for (int i = 0; i < digits_size; i++)
//        num *= 4;
//    combinations = malloc(sizeof(char*) * num);
//    combination = malloc(sizeof(char*) * digits_size);
//    backtrack(0);
//    *returnSize = combinations_size;
//    return combinations;
//}
//
//int main()
//{
//    int a = 0;
//    letterCombinations("2", &a);
//	return 0;
//}